package com.demo.树;

import cn.hutool.core.lang.Console;
import lombok.Getter;
import lombok.Setter;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Tree01 {

    public static void main(String[] args) {
        Integer[] pre = new Integer[]{1, 2, 4, 7, 3, 5, 6, 8, 9};
        Integer[] in = new Integer[]{4, 7, 2, 1, 5, 3, 8, 6, 9};
        // 根据先序和中序生成一颗二叉树
        TreeNode tree = createTree(pre, 0, pre.length - 1, in, 0, in.length - 1);

        Console.log("宽度（广度）优先遍历：");
        print广度(tree);
        System.out.println();
        String l, i, r;
        Console.log("先序序列化: {}", l = 先序序列化(tree));
        Console.log("中序序列化: {}", i = 中序序列化(tree));
        Console.log("后序序列化: {}", r = 后序序列化(tree));
        TreeNode lTree = 先序反序列化(l);
        Console.log("宽度（广度）优先遍历：");
        print广度(lTree);
        System.out.println();
        TreeNode rTree = 后序反序列化(r);
        Console.log("宽度（广度）优先遍历：");
        print广度(rTree);
        System.out.println();
        Console.log("证明是完全二叉树：{}", 证明是完全二叉树(lTree));
        Integer[] 完全二叉树 = new Integer[]{7, 8, 9, 1, 2, 4, 0, 5, 3};
        TreeNode tmp = getTreeByHead(完全二叉树);
        Console.log("证明是完全二叉树：{}", 证明是完全二叉树(tmp));
        Console.log("宽度（广度）优先遍历：");
        print广度(tmp);
        System.out.println();
        Console.log("证明是平衡二叉树：{}", 证明是平衡二叉树(lTree).isSbt);
        Console.log("证明是平衡二叉树：{}", 证明是平衡二叉树(tmp).isSbt);
        System.out.println();
        Console.log("证明是平衡二叉树：{}", 证明是满二叉树(lTree).isMt);
        Console.log("证明是平衡二叉树：{}", 证明是满二叉树(tmp).isMt);
        Console.log("证明是平衡二叉树：{}", 证明是满二叉树(getTreeByHead(new Integer[]{7, 8, 9, 1, 2, 4, 0})).isMt);
    }

    private static TreeNode 先序反序列化(String l) {
        Queue<String> queue = new LinkedList();
        for (String s : l.split("_")) {
            queue.offer(s);
        }
        return 先序反序列化(queue);
    }

    private static TreeNode 先序反序列化(Queue<String> queue) {
        String tmp = queue.poll();
        if (tmp == null || "#".equals(tmp)) {
            return null;
        }
        TreeNode node = new TreeNode(Integer.valueOf(tmp));
        node.left = 先序反序列化(queue);
        node.right = 先序反序列化(queue);
        return node;
    }


    private static TreeNode 后序反序列化(String r) {
        Stack<String> stack = new Stack<>();
        for (String s : r.split("_")) {
            stack.push(s);
        }
        return 后序反序列化(stack);
    }

    private static TreeNode 后序反序列化(Stack<String> stack) {
        if (stack.size() < 1) {
            return null;
        }
        String tmp = stack.pop();
        if ("#".equals(tmp)) {
            return null;
        }
        TreeNode node = new TreeNode(Integer.valueOf(tmp));
        node.right = 后序反序列化(stack);
        node.left = 后序反序列化(stack);
        return node;
    }

    public static String 先序序列化(TreeNode tree) {
        if (tree == null) {
            return "#_";
        }
        String str = tree.value + "_";
        str += 先序序列化(tree.left);
        str += 先序序列化(tree.right);
        return str;
    }

    public static String 中序序列化(TreeNode tree) {
        if (tree == null) {
            return "#_";
        }
        String str = "";
        str += 中序序列化(tree.left);
        str += tree.value + "_";
        str += 中序序列化(tree.right);
        return str;
    }

    public static String 后序序列化(TreeNode tree) {
        if (tree == null) {
            return "#_";
        }
        String str = "";
        str += 后序序列化(tree.left);
        str += 后序序列化(tree.right);
        str += tree.value + "_";
        return str;
    }

    public static void print广度(TreeNode tree) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(tree);
        TreeNode tmp = null;
        while ((tmp = queue.poll()) != null) {
            System.out.printf("%s  ", tmp.value);
            if (tmp.left != null) {
                queue.offer(tmp.left);
            }
            if (tmp.right != null) {
                queue.offer(tmp.right);
            }
        }
    }

    // 根据数组 做成一颗树
    public static TreeNode getTreeByHead(Integer[] data) {
        ArrayList<TreeNode> tmp = new ArrayList<>();
        for (int i = 0; i < data.length; i++) {
            tmp.add(new TreeNode(data[i]));
        }
        for (int i = 0; i < data.length; i++) {
            TreeNode node = tmp.get(i);
            int left = 0, right = 0;
            // 寻找左孩子
            if ((left = i * 2 + 1) < data.length) {
                node.left = tmp.get(left);
            } else {
                node.left = null;
            }
            // 寻找右孩子
            if ((right = left + 1) < data.length) {
                node.right = tmp.get(right);
            } else {
                node.right = null;
            }
        }
        return tmp.get(0);
    }

    // 1> 左子树必须是满二叉树，右子树也必须是满二叉树
    // 2> 节点个数 N 和最大深度 L 满足 $$ N = 2^L - 1 $$
    public static 满二叉Dp 证明是满二叉树(TreeNode tree) {
        if (tree == null) {
            return new 满二叉Dp(true, 0, 0);
        }
        满二叉Dp dp = new 满二叉Dp();
        满二叉Dp left = 证明是满二叉树(tree.left);
        满二叉Dp right = 证明是满二叉树(tree.right);
        dp.nodeNum = left.nodeNum +  right.nodeNum + 1;
        dp.height = Math.max(left.height, right.height) + 1;
        dp.isMt = left.isMt && right.isMt && dp.nodeNum == (2 << (dp.height - 1)) - 1;
        return dp;
    }

    public static class 满二叉Dp {
        public boolean isMt;
        public int height;
        public int nodeNum;
        public 满二叉Dp() {}
        public 满二叉Dp(boolean isSbt, int height, int nodeNum) {
            this.isMt = isSbt;
            this.height = height;
            this.nodeNum = nodeNum;
        }
    }

    // 1> 左子树必须是平衡二叉树，右子树也必须是平衡二叉树
    // 2> 左子树的高度与右子树的高度差不大于2
    public static 平衡Dp 证明是平衡二叉树(TreeNode tree) {
        if (tree == null) {
            return new 平衡Dp(true, 0);
        }
        平衡Dp dp = new 平衡Dp();
        平衡Dp left = 证明是平衡二叉树(tree.left);
        平衡Dp right = 证明是平衡二叉树(tree.right);
        dp.isSbt = left.isSbt && right.isSbt && Math.abs(left.height - right.height) < 2;
        dp.height = Math.max(left.height, right.height) + 1;
        return dp;
    }

    public static class 平衡Dp {
        public boolean isSbt;
        public int height;
        public 平衡Dp() {}
        public 平衡Dp(boolean isSbt, int height) {
            this.isSbt = isSbt;
            this.height = height;
        }
    }

    public static boolean 证明是完全二叉树(TreeNode tree) {
        if (tree == null) {
            return false;
        }
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(tree);
        TreeNode current = null;
        boolean isLeaf = false;
        while ((current = queue.poll()) != null) {
            if (isLeaf && current.left == null && current.right == null) {
                continue;
            }
            if (current.left != null && current.right != null) {
                queue.offer(current.left);
                queue.offer(current.right);
            } else if (current.left == null && current.right != null) {
                return false;
            } else if (current.left != null){
                // 左孩子不为空，右孩子为空
                queue.offer(current.left);
                isLeaf = true;
            } else {
                // 左右孩子都为空
                isLeaf = true;
            }
        }
        return true;
    }

    public static TreeNode createTree(Integer[] pre, int preL, int preR, Integer[] in, int inL, int inR) {
        if (preL > preR || inL > inR) {
            return null;
        }
        TreeNode node = new TreeNode(pre[preL]);
        Integer pivot = inL;
        while (!node.value.equals(in[pivot])) {
            pivot ++;
        }
        node.left = createTree(pre, preL + 1, preL + (pivot - inL), in, inL, pivot - 1);
        node.right = createTree(pre, preL + (pivot - inL) + 1, preR, in, pivot + 1, inR);
        return node;
    }

    @Getter
    @Setter
    public static class TreeNode {
        public Integer value;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(Integer datum) {
            this.value = datum;
        }
    }
}
